<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
   <TITLE>QDD : Some Quick Examples</TITLE>
   <META NAME="GENERATOR" CONTENT="Mozilla/3.04Gold (X11; I; Linux 2.0.36 i586) [Netscape]">
</HEAD>
<BODY TEXT="#000000" BGCOLOR="#FFFFFF" LINK="#009696" VLINK="#006464" ALINK="#404040">
     
<CENTER><h3><a name="TOP">Quick Examples</a></h3></CENTER><p>

<p><li><a href="#USE">Using QDD in a program</a>
<p><li><a href="#MUXADD">Example : Multiplexed Adder</a>
<p><li><a href="#SHORNUF">Example : the SHORNUF factoring algorithm</a>

<P>
<HR WIDTH="100%">
</P>

<CENTER><h3><a name="USE">Using QDD</a></h3></CENTER><p>
<p>
<CENTER><a href="#TOP">Back to Top</a></CENTER><p>

<FONT COLOR="#FF0000" SIZE=+1>To use QDD, add the following header to your program :</FONT>

<pre>
#include "qdd.h"
</PRE>

<FONT COLOR="#FF0000" SIZE=+1>And hack up the following Makefile :</FONT>

<PRE>
# --- Location of QDD/BDD package installation
QDDLOC = ..

# --- Location of QDD/BDD library
LIBDIR = $(QDDLOC)/lib

# --- Location of QDD/BDD package header
INCDIR = $(QDDLOC)/include

# --- Linker flags for use with QDD <FONT COLOR="#FF0000">(order and location *is* important)</FONT>
QDDFLAGS = -lqdd -lbdd -lm -lg++

# --- Compiler flags
CFLAGS = -g -O3 -Wall

# --- Your C++ compiler
CPP = g++

all: shornuf

shornuf: shornuf.o
	$(CPP) shornuf.o -L$(LIBDIR) $(QDDFLAGS) -o shornuf

shornuf.o: shornuf.cc
	$(CPP) $(CFLAGS) -c shornuf.cc -I$(INCDIR) -o shornuf.o
</PRE>

<P>
<HR WIDTH="100%">
</P>

<CENTER><h3><a name="MUXADD">QDD Example : A multiplexed adder (from <a href="http://tph.tuwien.ac.at/~oemer/qc/qcl/"> QCL</a>)</a></h3></CENTER><p>
<p>
<CENTER><a href="#TOP">Back to Top</a></CENTER><p>

<PRE>

void muxaddbit (int a0, int a1, QuantumBit &amp; sel, QuantumBit &amp; b, QuantumBit &amp; ci_sum, QuantumBit &amp; co, QuantumBit &amp; e, int dir) {

<FONT COLOR="#FF0000">// Note that the arguments here are object references.</FONT>
<FONT COLOR="#FF0000">// We don't allow QuantumBits/Registers to be copied at all.</FONT>
<FONT COLOR="#FF0000">// This helps guarantee quantum consitency in the model.</FONT>

<FONT COLOR="#FF0000">// We have to cheat to implement reversible operations :(</FONT>

  if (dir &gt; 0) {

<FONT COLOR="#FF0000">// Allocate a single quantum bit <b>M</b> with an initial value of 0.</FONT>

    QuantumBit M(0);

<FONT COLOR="#FF0000">
// The C++ "^=" operator has been overloaded to be the quantum XOR
// operator.  The C++ infix "&" allows accumulation of conditions for
// use in the quantum XOR.  In the following line, if the classical
// control signal a1 equals 1, then we will conditionally invert the
// quantum bit <b>M</b> in the quantum state where the quantum bits
// <b>e</b> and <b>sel</b> are true.
</FONT>

    if (a1) M ^= e &amp; sel;

<FONT COLOR="#FF0000">// Conditionally invert <b>M</b> if a0=1 when <b>e</b> is true and <b>sel</b> is false.</FONT>

    if (a0) M ^= e &amp; (! sel);

<FONT COLOR="#FF0000">// .. etc </FONT>

    ci_sum ^= e &amp; M;
    ci_sum ^= e &amp; b;

    co  ^= e &amp; M &amp; (! ci_sum);
    co  ^= e &amp; (! M) &amp; b &amp; (! ci_sum);
    co  ^= e &amp; M &amp; b &amp; ci_sum ;

<FONT COLOR="#FF0000">// Undo the operations performed on <b>M</b></FONT>

    if (a0) M ^= e &amp; (! sel);

    if (a1) M ^= e &amp; sel;

<FONT COLOR="#FF0000">// By the time we get here, M should be in a pure state ..</FONT>
<FONT COLOR="#FF0000">// in fact, it should be in its original (false) state.</FONT>
<FONT COLOR="#FF0000">// (which I could/should have tested for, I guess :)</FONT>

    try {
      M.unMixed();
    }
    catch (QuantumException e) {

<FONT COLOR="#FF0000">// This is really a violation of quantum computing rules .. You cannot</FONT>
<FONT COLOR="#FF0000">// "tell" if a bit is in a pure state.  Nonetheless, such tests are </FONT>
<FONT COLOR="#FF0000">// considered necessary during software development .. at least </FONT>
<FONT COLOR="#FF0000">// it helped me :)</FONT>


      cerr &lt;&lt; &quot;muxaddbit() : Mixed Bits\n&quot; ;
      throw e;
    }

<FONT COLOR="#FF0000">// At this point, C++ helps us do quantum garbage collection (automagically)</FONT>
<FONT COLOR="#FF0000">// Since <b>M</b> is in a pure state, we can reuse it later</FONT>

  }

  else {

<FONT COLOR="#FF0000">// The reverse operation.</FONT>

    QuantumBit M(0);

    if (a1) M ^= e &amp; sel;

    if (a0) M ^= e &amp; (! sel);

    co  ^= e &amp; M &amp; b &amp; ci_sum ;
    co  ^= e &amp; (! M) &amp; b &amp; (! ci_sum);
    co  ^= e &amp; M &amp; (! ci_sum);

    ci_sum ^= e &amp; b;
    ci_sum ^= e &amp; M;

    if (a0) M ^= e &amp; (! sel);

    if (a1) M ^= e &amp; sel;

    try {
      M.unMixed();
    }
    catch (QuantumException e) {
      cerr &lt;&lt; &quot;muxaddbit(-1) : Mixed Bits\n&quot; ;
      throw e;
    }

  }

}
</PRE>

<P>
<HR WIDTH="100%"></P>

<CENTER><h3><a name="SHORNUF">QDD Example : <B>SHORNUF</B> (based on routine from <a href="http://tph.tuwien.ac.at/~oemer/qc/qcl/"> QCL</a>)</a></h3></CENTER><p>
<p>
<CENTER><a href="#TOP">Back to Top</a></CENTER><p>

<PRE>

Integer shornuf(Integer Number) {

<FONT COLOR="#FF0000">// We use g++ <B>BIGNUM</B> Integers to make life easier when factoring <B>really</B> big numbers.

</FONT>  Integer Factor;
  Integer f1,f2;
  Integer A;
  Integer Cv;
  Integer Xv;

  int size = ilog2(Number);

  cout &lt;&lt; &quot;Bits : &quot; &lt;&lt; size &lt;&lt; &quot;\n&quot;;

<FONT COLOR="#FF0000">// Here we allocate a quantum register with <B>size</B> bits.

</FONT>  QuantumRegister F(size);
  Integer Fv;

  QuantumRegister X(size);
  Integer Pv;

  int attempt = 1;
  int found = 0;
  while ((attempt &lt; 8) &amp;&amp; (! found)) {

    cout &lt;&lt; &quot;Attempt # &quot; &lt;&lt; attempt &lt;&lt; &quot;\n&quot; ;

    do {
      
      A =  (rand(size) % Number) | 3 ;
    
    } while (gcd(Number,A) != 1) ;

    cout &lt;&lt; &quot;Random A : &quot; &lt;&lt; A &lt;&lt; &quot;\n&quot;;

<FONT COLOR="#FF0000">// Here we set the value of the <B>X</B> register to all zeros.

</FONT>    X.Set(0);

<FONT COLOR="#FF0000">// We then perform an <B>X.Mix()</B> to place the register in a superposition of states.

</FONT>    X.Mix();
            
    F.Set(0);

<FONT COLOR="#FF0000">// Perform Quantum Exponentiation (Wow!)

</FONT>    expn(A,Number,X,F, 1); // F = a^X mod n

<FONT COLOR="#FF0000">// Perform a classical sampling of <B>F</B>.  This collapses the entire quantum
// state so that it is consistant with the value measured in <B>F</B>.

</FONT>    Fv = F.Sample();

<FONT COLOR="#FF0000">// Measure the period of <B>X</B>.  Unfortunately, a bit of a quantum cheat.

</FONT>    Pv = X.Period();

    f1 = gcd((powmod(A,Pv/2,Number) + 1) % Number , Number) ;
    f2 = gcd((powmod(A,Pv/2,Number) + Number - 1) % Number , Number) ;

    Xv = X.Sample();

    Cv = powmod(A,Xv,Number);

    assert(Cv == Fv, &quot;Mismatch&quot;);

    f1 = gcd(Number,f1);
    f2 = gcd(Number,f2);

    Factor = (f1 &gt; f2 ? f1 : f2);

    found = (Factor &gt; 1) &amp;&amp; (Factor &lt; Number);

    attempt++;

  }

  return(Factor);

}
</PRE>

</BODY>
</HTML>
